#include<bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
const int N = 2e5 + 10;
#define INF 0x3f3f3f3f;
typedef long long int ll;
#define close(); std::ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);
//----------------------------------------------------------------------------//
int n;
void solve()
{
    cin >> n;
    string s;
    cin >> s;

    //s = ' ' + s;
    int cnt[10];

    int ans = 0;
    for(int i = 0; i < n; i++)
    {
        memset(cnt, 0, sizeof cnt);
        int mx = 0, dif = 0;
        for(int j = i; j < min(n, i + 100); j++)
        {
            if(++cnt[s[j] - '0'] == 1) dif++;
            mx = max(mx, cnt[s[j] - '0']);
            if(dif >= mx) ans++;
        }
    }
    cout << ans << '\n';


}

int main()
{
    close();
    int T;
    cin >> T;
    while (T--) solve();
    return 0;
}
//给定一个数字字符串，问其中有多少个子串，其不同数字的个数大于等于出现次数最多的数的次数。